/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：SkipList.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-05-11
Function List ：
Description   ：Deterministic Skip List
******************************************************/

#include "SkipList.h"
#include <stdlib.h>  // for malloc
#include "FatalError.h"

#define Infinity 65535

struct SkipNode {
    ElementType Element;
    SkipList    Right;
    SkipList    Down;
};

// Static Variable Lists
static Position Bottom = NULL;  /* Needs initialization */
static Position Tail   = NULL;  /* Needs initialization */

SkipList Initialize(void) {
    SkipList L;

    if (Bottom == NULL) {
        Bottom = (Position)malloc(sizeof(struct SkipNode));
        if (Bottom == NULL) {
            FatalError("Out of space!!!");
        } else {
            Bottom->Right = Bottom;
            Bottom->Down = Bottom;
        }

        Tail = (Position)malloc(sizeof(struct SkipNode));
        if (Tail == NULL) {
            FatalError("Out of space!!!");
        } else {
            Tail->Element = Infinity;
            Tail->Right = Tail;
        }
    }

    /* Create the header node */
    L = (SkipList)malloc(sizeof(struct SkipNode));
    if (L == NULL) {
        FatalError("Out of space!!!");
    } else {
        L->Element = Infinity;
        L->Right = Tail;
        L->Down = Bottom;
    }

    return L;
}

void Destroy(SkipList L) {
    MakeEmpty(L);
    free(L);
}

/* Memory reclamation is left as an exercise */
/* Hint: Delete from top level to bottom level */
SkipList MakeEmpty(SkipList L) {
    L->Right = Tail;
    L->Down = Bottom;

    return L;
}

int IsEmpty(SkipList L) {
    return L == NULL;
}

/* Return Position of node containing Item, */
/* or Bottom if not found */
Position Find(ElementType Item, SkipList L) {
    Position Current = L;

    Bottom->Element = Item;
    while (Item != Current->Element) {
        if (Item < Current->Element) {
            Current = Current->Down;
        } else {
            Current = Current->Right;
        }
    }

    return Current;
}

Position FindMin(SkipList L) {
    Position Current = L;

    while (Current->Down != Bottom) {
        Current = Current->Down;
    }

    return Current;
}

Position FindMax(SkipList L) {
    Position Current = L;

    while (Current->Right->Right != Tail || Current->Down != Bottom) {
        if (Current->Right->Right != Tail) {
            Current = Current->Right;
        } else {
            Current = Current->Down;
        }
    }

    return Current;
}

SkipList Insert(ElementType Item, SkipList L) {
    Position Current = L;
    Position NewNode;

    Bottom->Element = Item;
    while (Current != Bottom) {
        while (Item > Current->Element) {
            Current = Current->Right;
        }

        /* If gap size is 3 or at bottom level */
        /* and must insert, then promote the middle element */
        if (Current->Element > Current->Down->Right->Right->Element) {
            NewNode = (Position)malloc(sizeof(struct SkipNode));
            if (NewNode == NULL) {
                FatalError("Out of space!!!");
            } else {
                NewNode->Right = Current->Right;
                NewNode->Down = Current->Down->Right->Right;
                Current->Right = NewNode;
                NewNode->Element = Current->Element;
                Current->Element = Current->Down->Right->Element;
            }
        } else {
            Current = Current->Down;
        }
    }

    /* Raise height of DSL if necessary */
    if (L->Right != NULL) {
        NewNode = (Position)malloc(sizeof(struct SkipNode));
        if (NewNode == NULL) {
            FatalError("Out of space!!!");
        } else {
            NewNode->Down = L;
            NewNode->Right = Tail;
            NewNode->Element = Infinity;
            L = NewNode;
        }
    }

    return L;
}

SkipList Delete(ElementType Item, SkipList L) {
    return L;
}

ElementType Retrieve(Position P) {
    return P->Element;
}

// EOF

